home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / basic / doublhsh.bas < prev    next >
Encoding:
BASIC Source File  |  1990-03-24  |  7.4 KB  |  189 lines
  1. '
  2. '    Abstract
  3. '    --------
  4. '
  5. '    Double hashing is a useful method for data compression when
  6. '    it is necessary to search for strings previously encountered
  7. '    in the uncompressed data.  Double hashing performs better than
  8. '    linear probing when the hash table gets full, and is usually
  9. '    faster than linked lists.
  10. '
  11. '
  12. '    Description
  13. '    -----------
  14. '
  15. '    This double hashing method is in Power BASIC v 1.1 which
  16. '    supports modulus arithmetic on long and quad integers.
  17. '    The code was translated from the pseudo Pascal source code in
  18. '
  19. '         Robert Sedgewick.  ALGORITHMS.  Addison-Wesley.
  20. '         1983 ed.  pp 203/10.
  21. '
  22. '    and was modified to hash 32 K items into a table size of
  23. '    32 K entries, occupying about 64 K RAM for the table.
  24. '
  25. '    Of incidental interest to the method are the following lists
  26. '    of prime numbers near to but not exceeding the base-2 boundaries
  27. '    of 8 K, 16 K, 32 K, and 64 K.  (See the textbook for why.)
  28. '
  29. '        8101,  8111,  8117,  8123,  8147,  8161,  8171,  8179,  8191
  30. '
  31. '       16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381
  32. '
  33. '       32693, 32707, 32713, 32717, 32719, 32749
  34. '
  35. '       65497, 65519, 65521
  36. '
  37. '
  38. '    For more details and other data compression material, contact:
  39. '
  40. '    Colin James III, CQA
  41. '    Certified Quality Analyst
  42. '    1975 Oak St, #4
  43. '    Lakewood, CO  80215-2737
  44. '
  45. '    DATA:  (303) 234 - 0085  CEC Services BBS, 9600 V.32c MNP 9, 8-N-1
  46. '
  47. '            Specializing in: data compression, Ada, BASIC,
  48. '                             SQA/SQC, and DoD-STD-2167A
  49. '
  50. '            New callers may download the public catalog list
  51. '            of files (occupying about 130 MB of over 2 GB).
  52. '
  53. '            Subscription for general access is $ 10 per month.
  54. '
  55. '            Specialty access to compression source code is $150
  56. '            per month where a significant, two-pass improvement on
  57. '            LZW has been developed as LZJ, is now available, and
  58. '            when a generalized mathematical description is completed
  59. '            is due to be patented as an unique apparatus.
  60. '            (LZJ compresses about 15 % better than the products now
  61. '            available;  speed is relatively faster in the PC model.)
  62. '
  63. '            Please note:
  64. '            CEC Services can NOT be reached on either of the
  65. '            major computer services, only at the number above.
  66. '
  67. '    VOICE: (303) 234 - 0084  ( 4 PM to 8 PM Mountain Time  O N L Y )
  68. '
  69. ' ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  70. '
  71. ' Double-Hash  v 02
  72. ' -----------
  73. '
  74. ' Copr 1990, Colin James III  All Rights Reserved
  75. '         Permission to copy is hereby granted
  76.  
  77. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  78. ' set up data type definitions
  79. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  80.  
  81. DEFINT I                               ' define I for      integers
  82. DEFLNG L                               ' define L for long integers
  83.  
  84.  
  85. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  86. ' set up Lempel-Ziv [ LZ ] table data structure
  87. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  88.  
  89. DIM I.LZ.prefix ( 0: 32766)            ' LZ codes are broken into prefix
  90.                        '    codes or sequence numbers of
  91.                        '    15-bits ( 0 ... 32766)
  92. DIM I.LZ.suffix ( 0: 32766)            ' and suffix codes or input bytes
  93.                        '    following the prefix
  94. '
  95. ' Two integer arrays are used due to the single array size limitation of
  96. ' 64 K in Power BASIC (the successor to Turbo BASIC).  Indexing is the
  97. ' same in the respective arrays.  The sequential codes entered into the
  98. ' arrays could of course be output as variable length codes as the method
  99. ' Lempel-Ziv-Welch or LZW.  (The variable code would be the prefix only,
  100. ' followed by an 8-bit byte suffix.)  These arrays are necessary to have
  101. ' below for checking a hash hit.  As Sedgewick notes, a hash table which
  102. ' is about 90% full can take 50 compares for a linear probe but only 10
  103. ' compares with double hashing.
  104.  
  105.  
  106. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  107. ' set up hash table
  108. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  109.  
  110. LET I.prime.max = 32719                ' large prime for hash table size = M
  111. LET I.prime.nxt = I.prime.max - 2      ' secondary hash increment = M - 2
  112. LET I.hasht.max = I.prime.max          ' max size of hash table
  113. LET I.hasht.min = 0                    ' min size of hash table
  114.  
  115. DIM I.hash.table( I.hasht.min: I.hasht.max)
  116.                        ' long int hash table, 0 ... 32719
  117.  
  118. LET L.max.val = ( 2 ^ 22) - 1          ' largest numeric value to hash
  119.                        '    is 8,388,607
  120. LET I.sen.val = 32767                  ' sentinel value > i.hasht.max
  121.  
  122. FOR I = 0 TO I.hasht.max               ' loop to initialize hash table to
  123.    LET I.hash.table( I) = I.sen.val    '   sentinel value of 32767
  124. NEXT i
  125.  
  126. LET I.prefix = 0                       ' initialize prefix code to a
  127.                        '    sequence number of zero
  128. LET I.seq.no = -1                      ' initialize sequence number so
  129.                        '    that subsequent increment of
  130.                        '    seq no + 1 (or 0) is the first
  131.  
  132. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  133. ' get next input byte to compress
  134. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  135.  
  136. LET I.prefix = 8191                    ' sample prefix value is an arbitrary
  137.                        '    sequence number in the LZW table
  138.                        '    and refers to a compressed string
  139. LET I.suffix =  255                    ' next input byte to compress
  140.  
  141. LET L.search.val = I.prefix * 256 + I.suffix
  142.                        ' this builds a numeric value to hash
  143.                        ' ( = 2,097,151)
  144.  
  145. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  146. ' hashsearch
  147. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  148.  
  149. LET I.hash01 = L.search.val MOD I.prime.max
  150.                        ' first hash value calculated
  151.  
  152. LET I.hash02 = I.prime.nxt - ( L.search.val MOD I.prime.nxt)
  153.                        ' second hash value calculated
  154. LET I.hash03  = I.has01                ' third  hash value initialized
  155.  
  156. WHILE (              I.hash.table( I.hash03)  <> I.sen.val) _
  157.   AND ( I.LZ.prefix( I.hash.table( I.hash03)) <> I.prefix ) _
  158.   AND ( I.LZ.suffix( I.hash.table( I.hash03)) <> I.suffix )
  159.                        ' this loop searches for the next
  160.                        '    available empty hash slot
  161.    LET I.hash03 = ( I.hash03 + I.hash02) MOD I.prime.max
  162. WEND
  163.  
  164. LET I.hash.result = I.hash.table( I.hash03)
  165.  
  166. IF I.hash.result <> I.sen.val THEN
  167.    LET I.prefix = I.hash.result        ' result is the sequence no
  168. ELSE
  169.    LET I.seq.no = I.seq.no + 1         ' increment sequence no of the
  170.                        '    next code to be inserted
  171.    LET I.hash.table( I.hash03) = I.seq.no
  172.                        ' insert sequence no of code
  173.                        '   into hash table
  174.    LET I.LZ.prefix( I.seq.no) = I.prefix
  175.                        ' build compression output table
  176.    LET I.LZ.suffix( I.seq.no) = I.suffix
  177.                        ' build compression output table
  178.    LET I.prefix = 0                    ' clear prefix code
  179. END IF
  180.  
  181.  
  182. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  183. 'jump where next byte is input for compression & prefix + suffix catenated
  184. ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  185.  
  186. END
  187.  
  188.  
  189.